package com.company.OfferGuide;

public class 斐波那契数列 {

    public int fib(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n+1];

        for (int i = 1; i < dp.length; i++) {
            if (i == 1 || i == 2) dp[i] = 1;
            else {
                dp[i] = dp[i - 1] + dp[i - 2];
                if (dp[i] > 1000000007) {
                    dp[i] = dp[i] % 1000000007;
                }
            }
        }

        return dp[n];
    }

}
